package com.ljy.my_study.leetcode.删除排序链表中的重复元素II;

import com.ljy.my_study.util.ListNodeUtil;
import com.ljy.my_study.util.ListNodeUtil.*;

import java.util.HashMap;
import java.util.Map;

/**
 * @author lijunying
 * @date 2021/3/25 14:11
 */
public class TestMain {

//    存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
//
//    返回同样按升序排列的结果链表。
//
//             
//
//    示例 1：
//
//
//    输入：head = [1,2,3,3,4,4,5]
//    输出：[1,2,5]
//    示例 2：
//
//
//    输入：head = [1,1,1,2,3]
//    输出：[2,3]
//             
//
//    提示：
//
//    链表中节点数目在范围 [0, 300] 内
//-100 <= Node.val <= 100
//    题目数据保证链表已经按升序排列
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        TestMain testMain=new TestMain();
        int[] array=new int[]{1,2,2,3,3,5,6};
        ListNode head=ListNodeUtil.createListNode(array);
        System.out.println(testMain.deleteDuplicates(head));
    }

    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        Map<Integer,Integer> map=new HashMap<>();
        ListNode node=head;
        while(node!=null){
            map.put(node.val,map.getOrDefault(node.val,0)+1);
            node=node.next;
        }
        node=head;
        ListNode newHead=null;
        ListNode preNode=null;
        while(node!=null){
            if(map.get(node.val)!=1){
                node=node.next;
                continue;
            }
            if(newHead==null){
                newHead=node;
            }
            if(preNode==null){
                preNode=node;
            }else{
                preNode.next=node;
                preNode=node;
            }
            node=node.next;
        }
        if(preNode!=null){
            preNode.next=null;
        }
        return newHead;
    }
//    public ListNode deleteDuplicates(ListNode head) {
//        if(head==null||head.next==null){
//            return head;
//        }
//        ListNode node=findHead(head);
//        head=node;
//        ListNode preNode=head;
//        while(node!=null){
//            if(node.next==null){
//                break;
//            }
//            if(node.next!=null&&node.val==node.next.val){
//                if(node.next.next!=null&&node.next.val!=node.next.next.val){
//                    node=node.next.next;
//                }else{
//                    node=node.next;
//                }
//            }else {
//                if(node.next.next!=null&&node.next.val==node.next.next.val){
//                    node=node.next.next;
//                }else{
//                    node=node.next;
//                }
//                if(preNode!=node){
//                    preNode.next=node;
//                }
//                node=node.next;
//                preNode=node;
//            }
//        }
//        return head;
//    }

    private ListNode findHead(ListNode head){
        boolean isChangeHead=false;
        ListNode node=head;
        while(node!=null&&node.next!=null){
            if(node.val==node.next.val){
                node=node.next;
                isChangeHead=true;
                continue;
            }else{
                if(node.next.next!=null&&node.next.val==node.next.next.val){
                    node=node.next.next;
                    isChangeHead=true;
                    continue;
                }
            }
            break;
        }
        if(isChangeHead){
            if(node==null||node.next==null){
                return null;
            }
            node=node.next;
        }
        return node;
    }

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
}
